//双向非循环不带头结点链表
//F1更好，既然是双向链表，就用好双向链表的优势
//不要再找前驱了，cur直接走到那个地方就可以
/**
 * remove：定义一个变量cur 走到cur 通过cur.val == val 判断是否相等 需要考虑头结点和尾结点
 * removeAllKey:定义一个变量cur 走到cur 通过cur.val == val 判断是否相等 需要考虑头结点和尾结点
 */
public class MyLinkedList {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val){
            this.val = val;
        }
        public ListNode(){

        }
    }
    public ListNode head;
    public ListNode tail;
    //打印链表中的值
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //输出链表的长度
    public int size(){
        ListNode cur = this.head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //判断链表中是否包含某个值key
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.tail == null){
            this.head = node;
            this.tail = node;
        }else{
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
    }
    //任意位置插入法
    public void addIndex(int index,int data){
        //先判断index的合法性
        if(index < 0 || index > size()){
            System.out.println("不合法！");
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        //F1 - cur 为要删除的结点
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
        //F2 - cur 要删除的结点的前驱
       /* while(index-1 != 0) {
            cur = cur.next;
            index--;
        }
        ListNode curNext = cur.next;
        node.next = curNext;
        curNext.prev = node;
        cur.next = node;
        node.prev = cur;*/

    }
    //删除第一次出现的某个值key

    //F1 - cur为要删除的结点
    public void remove(int key){
        ListNode cur = this.head;
        //特殊情况
        //1.空链表情况
        if(head == null){
            return;
        }
        //2.要删除的结点为头结点
        if(head.val == key){
            //2.1链表中只有头结点这一个结点
            if(head.next == null){
               head = null;
               tail = null;//别忘把tail也置空
            }else{//2.2链表中有多个结点
                head.next.prev = null;
                head = head.next;
            }
            return;
        }
        //先找到要删除的值
       while(cur != null){
           if(cur.val == key){
               //要删除的结点不为尾结点
               if(cur.next != null){
                   cur.prev.next = cur.next;
                   cur.next.prev = cur.prev;
               }else{ //要删除的结点为尾结点
                   tail.prev.next = null;
                   tail = tail.prev;
               }
               return;
           }
           cur = cur.next;
       }
    }
    //F2 - cur为要删除的结点的前驱
    public void removeOne(int key){
        ListNode cur = this.head;
        //1.链表为空链表
        if(this.head == null){
            return;
        }
        //删除的为头结点
        if(this.head.val == key){
            if(head.next == null){
               this.head = null;
               this.tail = null;
            }else{
                this.head = this.head.next;
                head.prev = null;
            }
            return;
        }
        while(cur.next != null){
            if(cur.next.val == key){
                if(cur.next.next != null){
                    cur.next = cur.next.next;
                    cur.next.next.prev = cur;
                }else{
                    tail = tail.prev;
                    tail.next = null;
                }
                return;
            }
            cur = cur.next;
        }
    }

    //删除链表中某个值key的所有
    //F2 - 可以搞个虚拟的头结点和尾结点，当成中间的删，就可以不考虑头结点和尾结点的情况了
    public void removeAllTheKey(int key){
       ListNode prev = new ListNode();
       ListNode last = new ListNode();
       if(head == null){
           return;
       }
       prev.next = head;
       head.prev = prev;
       head = prev;
       tail.next = last;
       last.prev = tail;
       tail = last;
       ListNode cur = this.head;
       while(cur.next != null){
           cur = cur.next;
           if(cur.val == key) {
               cur.prev.next = cur.next;
               cur.next.prev = cur.prev;
           }
       }
       head = head.next;
       if(head.next == null){
           head = null;
           tail = null;
           return;
       }
       head.prev = null;
       tail = tail.prev;
       tail.next = null;
    }
    //F1

    public void removeAllKey(int key){
        if(head == null){
            return;
        }
        //判断第一个结点是否为要删除的结点

        //找到第一个结点
        while(head.prev == null){
            //判断是否为要删除的结点
            if(head.val == key){
                //判断是只有这个一个结点，还是还有几点
                if(head.next == null){
                    head = null;
                    tail = null;
                    return;
                }else {
                    head = head.next;
                    head.prev = null;
                }
            }else{
                break;
            }
        }
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){//尾巴结点为要删的值
                if(cur.next == null){
                    tail.prev.next = null;
                    tail = tail.prev;
                    return;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    cur = cur.next;
                }
            }else{
                cur = cur.next;
            }

        }
    }
    //老师的做法
    public void removeOneKey(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                if(head == cur){
                    head = head.next;
                    if(head == null){
                        tail = null;
                        return;
                    }
                    head.prev = null;
                }else {
                    cur.prev.next = cur.next;
                    if (cur.next == null) {
                        tail = tail.prev;
                        tail.next = null;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }
    //老师的做法
    public void removeAll(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                if(head == cur){
                    head = head.next;
                    if(head == null){
                        tail = null;
                        return;
                    }
                    head.prev = null;
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next == null){
                        tail = tail.prev;
                        tail.next = null;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
    public void clear(){
        if(head == null){
            return;
        }
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
       }
        head = null;
        tail = null;
    }
}
